package utils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * <p>
 * 排序工具类
 * </p>
 *
 * @author AJun
 * @since 2020/8/2
 */
@SuppressWarnings({"DuplicatedCode", "ManualArrayCopy", "UnnecessaryLocalVariable"})
public class SortingUtil {

    public static boolean debug = true;

    private SortingUtil() {

    }

    /* -------以下是排序算法-------- */

    /**
     * 交换排序: 冒泡排序
     * <p>
     * 时间复杂度: O(n^2)
     * 最好情况: O(n)
     * 最坏情况: O(n^2)
     * 空间复杂度: O(1)
     * 稳定性: 稳定
     * </p>
     */
    public static void bubbleSort(int[] array) {
        int len = array.length;
        for (int end = len - 1; end > 0; end--) {
            // 记录最后一次交换的位置，默认设为 1，这个初始值在数组完全有序时有用
            int sortedIndex = 1;
            for (int begin = 1; begin <= end; begin++) {
                if (array[begin] < array[begin - 1]) {
                    swap(array, begin, begin - 1);
                    sortedIndex = begin; // 最后一次交换的位置
                }
            }
            end = sortedIndex; // 下一趟只扫描到 最后一次交换的位置

            debug(array);
        }
    }

    /**
     * 选择排序: 直接选择排序
     * <p>
     * 时间复杂度: O(n^2)
     * 最好情况: O(n^2)
     * 最坏情况: O(n^2)
     * 空间复杂度: O(1)
     * 稳定性: 不稳定
     * </p>
     */
    public static void selectionSort(int[] array) {
        int len = array.length;
        for (int end = len - 1; end > 0; end--) {
            int maxIndex = 0;
            for (int begin = 1; begin <= end; begin++) {
                if (array[maxIndex] <= array[begin]) {
                    maxIndex = begin;
                }
            }
            swap(array, maxIndex, end);

            debug(array);
        }
    }

    /**
     * 堆排序
     * <p>
     * 堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。
     * 这种数据结构具有以下性质。 任意节点小于它的所有后裔，最小元在堆的根上（堆序性）。堆总是一棵完全树。
     * 1.每次从数组添加一个元素来创建堆
     * 2.通过重复从堆中删除根
     * 3.重建堆来对数组排序
     * </p>
     * <p>
     * 时间复杂度: O(nlog(2)n)
     * 最好情况: O(nlog(2)n)
     * 最坏情况: O(nlog(2)n)
     * 空间复杂度: O(1)
     * 稳定性: 不稳定
     * </p>
     */
    public static void heapSort(int[] array) {
        // 原地建堆，自下而上的下滤，推荐这种，效率较高 O(n)
        int heapSize = array.length;
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            siftDown(i, array, heapSize);
        }

        while (heapSize > 1) {
            // 交换堆顶和尾部元素
            swap(array, 0, --heapSize);
            // 对 0 位置元素进行 siftDown(恢复堆的性质)
            siftDown(0, array, heapSize);

            debug(array);
        }
    }

    /**
     * 下滤，重建堆，恢复堆的性质，让 index 位置的元素下滤
     *
     * @param index 元素索引
     */
    private static void siftDown(int index, int[] array, int heapSize) {
        int element = array[index];
        int half = heapSize >> 1; // 公式
        // 必须保证 index 位置是非叶子节点，第一个叶子节点的索引就是非叶子节点的数量
        while (index < half) {
            // 默认使用左子节点和要删除的元素进行比较
            int childIndex = (index << 1) + 1; // 公式
            int child = array[childIndex];
            // 右子节点
            int rightIndex = childIndex + 1;
            // 选出左右子节点最大的
            if ((rightIndex < heapSize) && (array[rightIndex] - child > 0))
                child = array[childIndex = rightIndex];
            // 要删除元素大于子节点元素
            if (element - child >= 0)
                break;
            // 要删除元素小于子节点元素，将子节点存放到 index 位置
            array[index] = child;
            // 重新对 index 赋值
            index = childIndex;
        }
        array[index] = element;
    }

    /**
     * 插入排序
     * <p>
     * 时间复杂度: O(n^2)
     * 最好情况: O(n)
     * 最坏情况: O(n^2)
     * 空间复杂度: O(1)
     * 稳定性: 稳定
     * </p>
     */
    public static void insertionSort(int[] array) {
        for (int begin = 1; begin < array.length; begin++) {
            int sentinel = array[begin];
            int insertIndex = search(array, begin);
            for (int i = begin; i > insertIndex; i--) {
                array[i] = array[i - 1];
            }
            array[insertIndex] = sentinel;

            debug(array);
        }
    }

    /**
     * 利用二分搜索找到 index 位置元素的待插入位置
     * 已经排好序数组的区间范围是 [0, index)
     */
    private static int search(int[] array, int index) {
        int begin = 0;
        int end = index;
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (array[index] < array[mid]) {
                end = mid;
            } else {
                begin = mid + 1;
            }
        }
        return begin;
    }

    /**
     * 归并排序(递归实现)
     * <p>
     * 时间复杂度: O(nlog(2)n)
     * 最好情况: O(nlog(2)n)
     * 最坏情况: O(nlog(2)n)
     * 空间复杂度: O(n)
     * 稳定性: 稳定
     * </p>
     */
    public static void mergeSort(int[] array) {
        sort(array, 0, array.length);
    }

    /**
     * 对 [begin, end) 范围的数据进行归并排序
     */
    private static void sort(int[] array, int begin, int end) {
        // 只有一个元素则无需排序
        if (end - begin < 2) {
            return;
        }

        int mid = (begin + end) >> 1;
        // divide
        sort(array, begin, mid);
        sort(array, mid, end);
        // merge
        merge(array, begin, mid, end);

        debug(array);
    }

    /**
     * 对 [begin, mid) 和 [mid, end) 范围的序列合并为一个有序序列
     */
    private static void merge(int[] array, int begin, int mid, int end) {
        int[] leftArray = new int[array.length >> 1];
        int li = 0, le = mid - begin;
        int ri = mid, re = end;
        int ai = begin;

        // 备份左边数组
        for (int i = li; i < le; i++) {
            leftArray[i] = array[begin + i];
        }

        // 如果左边还没有结束
        while (li < le) {
            if (ri < re && array[ri] < leftArray[li]) {
                // 如果右边还没有结束，且右边元素小于左边，则直接用右边的ri位置元素覆盖掉ai位置元素
                array[ai++] = array[ri++];
            } else {
                // 如果右边已经结束，则直接用左边的li位置元素覆盖掉ai位置元素
                array[ai++] = leftArray[li++];
            }
        }
    }

    /**
     * 快速排序：对所有元素排序(递归实现)
     * <p>
     * 时间复杂度: O(nlog(2)n)
     * 最好情况: O(nlog(2)n)
     * 最坏情况: O(n^2)
     * 空间复杂度: O(log(2)n)
     * 稳定性: 不稳定
     * </p>
     */
    public static void quickSort(int[] array) {
        quickSort(array, 0, array.length);
    }

    /**
     * 快速排序：对某个区间的元素进行排序。
     */
    public static void quickSort(int[] array, int begin, int end) {
        if (end - begin < 2) {
            return;
        }

        // 确定轴点位置 O(n)
        int mid = pivotIndex(array, begin, end);
        // 对子序列进行快速排序
        quickSort(array, begin, mid);
        quickSort(array, mid + 1, end);
    }

    /**
     * 快速排序：构造出 [begin, end) 范围的轴点元素 (轴点构造)
     *
     * @param begin 开始索引
     * @param end   结束索引
     * @return 轴点元素的最终位置
     */
    private static int pivotIndex(int[] array, int begin, int end) {
        // 随机选择轴点元素，使得轴点左右元素数量尽可能保持均匀，范围 [begin, end)
        swap(array, begin, (int) (begin + Math.random() * (end - begin)));
        // 备份 begin 位置的元素(轴点元素)
        int pivot = array[begin];
        // end 指向最后一个元素
        end--;

        // 轴点元素构造
        while (begin < end) {
            while (begin < end) {
                if (pivot < array[end]) {
                    // 右边元素大于轴点元素
                    end--;
                } else {
                    // 右边元素小于等于轴点元素
                    array[begin++] = array[end];
                    break;
                }
            }

            while (begin < end) {
                if (pivot > array[begin]) {
                    // 左边元素小于轴点元素
                    begin++;
                } else {
                    // 左边元素大于等于轴点元素
                    array[end--] = array[begin];
                    break;
                }
            }
        }

        // 将轴点元素放到最终位置
        array[begin] = pivot;
        // 返回轴点元素
        return begin;
    }

    /**
     * 希尔(shell)排序
     * <p>
     * 时间复杂度: 取决于步长序列
     * 最好情况: O(n)
     * 最坏情况: O(n^4/3) ~ O(n^2)
     * 空间复杂度: O(1)
     * 稳定性: 不稳定
     * </p>
     */
    public static void shellSort(int[] array) {
        // 步长序列
        // List<Integer> stepSequence = shellStepSequence();
        List<Integer> stepSequence = sedgewickStepSequence(array);
        for (Integer step : stepSequence) {
            shellSort(array, step);
            debug(array);
        }
    }

    /**
     * 分成 step 列来进行排序
     *
     * @param step 步长
     */
    private static void shellSort(int[] array, int step) {
        // col: 第几列
        for (int col = 0; col < step; col++) {
            // 对第 col 列进行插入排序 (索引换算: col + row * step)
            for (int begin = col + step; begin < array.length; begin += step) {
                int cur = begin;
                while (cur > col && array[cur] < array[cur - step]) {
                    swap(array, cur, cur - step);
                    cur -= step;
                }
            }
        }
    }

    /**
     * 希尔的步长序列 (n / 2^k)，比如 n 为16时，步长序列是{1, 2, 4, 8}
     *
     * @return 步长序列
     */
    private static List<Integer> shellStepSequence(int[] array) {
        List<Integer> stepSequence = new ArrayList<>();
        int step = array.length;
        while ((step >>= 1) > 0) {
            stepSequence.add(step);
        }
        return stepSequence;
    }

    /**
     * Robert Sedgewick 提供的步长公式
     *
     * @return 步长序列
     */
    private static List<Integer> sedgewickStepSequence(int[] array) {
        List<Integer> stepSequence = new LinkedList<>();
        int step;
        int k = 0;
        while (true) {
            if (k % 2 == 0) {
                int pow = (int) Math.pow(2, k >> 1);
                step = 1 + 9 * (pow * pow - pow);
            } else {
                int pow1 = (int) Math.pow(2, (k - 1) >> 1);
                int pow2 = (int) Math.pow(2, (k + 1) >> 1);
                step = 1 + 8 * pow1 * pow2 - 6 * pow2;
            }
            if (step >= array.length)
                break;
            stepSequence.add(0, step);
            k++;
        }
        return stepSequence;
    }

    /**
     * 计数排序
     * <p>
     * 时间复杂度: O(n + k)
     * 最好情况: O(n + k)
     * 最坏情况: O(n + k)
     * 空间复杂度: O(n + k)
     * 稳定性: 稳定
     * 注: k 是整数的取值范围
     * </p>
     */
    public static void countingSort(int[] array) {
        // 找出最值
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }

        // 开辟内存空间，存储次数
        int[] counts = new int[max - min + 1];
        // 统计每个整数出现的次数
        for (Integer num : array) {
            counts[num - min]++;
        }
        // 累加次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        // 从后往前遍历元素，将它放到有序数组中的合适位置
        int[] newArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            newArray[--counts[array[i] - min]] = array[i];
        }

        // 将有序数组赋值到array
        for (int i = 0; i < newArray.length; i++) {
            array[i] = newArray[i];
        }
    }

    /**
     * 基数排序
     * <p>
     * 时间复杂度: O(d * (n + k))
     * 最好情况: O(d * (n + k))
     * 最坏情况: O(d * (n + k))
     * 空间复杂度: O(n + k)
     * 稳定性: 稳定
     * 注: d 是最大值的位数; k 是进制
     * </p>
     */
    public static void radixSort(int[] array) {
        // 找出最大值
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }

        // 个位数: array[i] / 1 % 10 = 3
        // 十位数：array[i] / 10 % 10 = 9
        // 百位数：array[i] / 100 % 10 = 5
        // 千位数：array[i] / 1000 % 10 = ...

        // 从个位开始，对数组进行排序
        for (int divider = 1; divider <= max; divider *= 10) {
            // 开辟内存空间，存储次数
            int[] counts = new int[10];
            // 统计每个整数出现的次数
            for (Integer num : array) {
                counts[num / divider % 10]++;
            }
            // 累加次数
            for (int i = 1; i < counts.length; i++) {
                counts[i] += counts[i - 1];
            }

            // 从后往前遍历元素，将它放到有序数组中的合适位置
            int[] newArray = new int[array.length];
            for (int i = array.length - 1; i >= 0; i--) {
                newArray[--counts[array[i] / divider % 10]] = array[i];
            }

            // 将有序数组赋值到array
            for (int i = 0; i < newArray.length; i++) {
                array[i] = newArray[i];
            }
        }
    }

    /**
     * 桶排序
     * <p>
     * 时间复杂度: O(n + k)
     * 最好情况: O(n + k)
     * 最坏情况: O(n + k)
     * 空间复杂度: O(n + m)
     * 稳定性: 稳定
     * 注: m 是桶的数量; k 为 n * logn - n + logm
     * </p>
     */
    @SuppressWarnings("unchecked")
    public static void bucketSort(int[] array) {
        List<Integer>[] buckets = new List[array.length];
        for (Integer i : array) {
            int bucketIndex = i / array.length;
            List<Integer> bucket = buckets[bucketIndex];
            if (bucket == null) {
                bucket = new LinkedList<>();
                buckets[bucketIndex] = bucket;
            }
            bucket.add(i);
        }

        // 对每个桶进行排序
        int index = 0;
        for (List<Integer> bucket : buckets) {
            if (bucket == null) {
                continue;
            }
            Collections.sort(bucket);
            for (Integer i : bucket) {
                array[index++] = i;
            }
        }
    }

    /* -------以下是工具方法-------- */

    /**
     * 交换数组中的2个元素
     *
     * @param array 数组
     * @param i     第1个索引
     * @param j     第2个索引
     */
    private static void swap(int[] array, int i, int j) {
        if (array == null || array.length == 1) {
            return;
        }
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 如果是debug模式，打印数组
     */
    private static void debug(int[] array) {
        if (!debug) return;
        System.out.print("[debug] => ");
        Tools.println(array);
    }

}
